#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define NUM 16384000 
//#define DEBUG

int partition(long* array, int i, int j) {
    long pivot = array[i];
    while (i < j) {
        while (i < j && pivot <= array[j])
            --j;
        array[i] = array[j];
        while (i < j && array[i] <= pivot)
            ++i;
        array[j] = array[i];
    }
    array[i] = pivot;
    return i;
}

void quick_sort(long* array, int* stack_l, int * stack_r, int len) {
    if (len <= 0)
        return;

    int idx = 0;
    int s = 0;
    int e = len - 1;
    int m;

    stack_l[idx] = s;
    stack_r[idx++] = e;

    while (idx > 0) {
        s = stack_l[--idx];
        e = stack_r[idx];
        
        m = partition(array, s, e);
        if (s < m - 1) {
            stack_l[idx] = s;
            stack_r[idx++] = m - 1;
        }
        if (m + 1 < e) {
            stack_l[idx] = m + 1;
            stack_r[idx++] = e;
        }
    }
}

int main() {
    long* array = (long *)malloc(NUM * sizeof(long));
    int i;
    int* stack_l = (int *)malloc(NUM * sizeof(int));
    int* stack_r = (int *)malloc(NUM * sizeof(int));
    clock_t start, end;
    double duration;

    srand(time(0));
    for (i = 0; i < NUM; ++i)
        array[i] = rand() % (10 * NUM);

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    start = clock();
    quick_sort(array, stack_l, stack_r, NUM);
    end = clock();

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    duration = (double)(end - start);
    printf("%.8f\n", (duration / CLOCKS_PER_SEC));

    return 0;
}


